#include <iostream>
#include <vector>
template <typename T> void insert_sort(std::vector<T> &v) {
  // 插入排序: 从未排序区域拿到一个元素，将其插入至已排序区域中的合适位置
  // 已排序区域
  for (int i = 1; i < v.size(); i++) {
    // 选择的值
    T value = v[i];
    // 遍历排序区域 找到第一个比他小的值，放在这个值的后面
    for (int j = i - 1; j >= 0; j--) {
      // 找到位置
      if (v[j] < value) {
        v[j + 1] = value;
        break;
        // 移动数据寻找合适的位置
      } else {
        v[j + 1] = v[j];
        v[j] = value;
      }
    }
  }
}

int main() {
  std::vector<int> list = {9, 8, 6, 4, 5, 3, 1, 2};
  insert_sort<int>(list);
  for (int &i : list) {
    std::cout << i;
  }

  return 0;
}